package 算法.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
 *
 * @author lchenglong
 * @date 2022/3/21
 */
public class Offer12 {

    public static void main(String[] args) {
        Offer12 instance = new Offer12();
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";
        boolean ans = instance.exist(board, word);
        System.out.println(ans);
    }
    char[][] board;
    char[] words;
    public boolean exist(char[][] board, String word) {
        this.words = word.toCharArray();
        this.board = board;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(i, j, 0)) return true;
            }
        }
        return false;
    }

    /**
     * 深度优先搜索
     * @param i
     * @param j
     * @param k
     * @return
     */
    boolean dfs( int i, int j, int k) {
        // 到达边界条件，超出数组边界或者不匹配
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]) return false;
        // 匹配成功
        if(k == words.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
                dfs( i, j + 1, k + 1) || dfs( i , j - 1, k + 1);
        board[i][j] = words[k];
        return res;
    }
}
